package com.yxp.middle;

import com.yxp.util.TreeNode;

/**
 * @author : yang.xp
 * @date : 2021/8/18 12:21
 * @description : 1008. 前序遍历构造二叉搜索树
 * 输入：[8,5,1,7,10,12]
 */
public class Problem1008 {

    public static void main(String[] args) {
        int[] numbers = new int[]{8, 5, 1, 7, 10, 12};
        Problem1008 problem1008 = new Problem1008();
        problem1008.bstFromPreorder(numbers);
    }

    public TreeNode bstFromPreorder(int[] numbers) {
        TreeNode root = null;
        // 此处的root 永远是根节点8
        for (int i = 0; i < numbers.length; i++) {
            root = add(root, numbers[i]);
        }
        return root;
    }

    public TreeNode add(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }
        if (root.val > val) {
            root.left = add(root.left, val);
        } else {
            root.right = add(root.right, val);
        }
        return root;
    }

















//    public TreeNode bstFromPreorder(int[] preorder) {
//        TreeNode root = null;
//        for (int i = 0; i < preorder.length; i++) {
//            root = add(root, preorder[i]);
//        }
//        return root;
//    }
//
//    public TreeNode add(TreeNode root, int num) {
//        if (root == null) {
//            return new TreeNode(num);
//        }
//        if (root.val > num) {
//            root.left = add(root.left, num);
//        } else {
//            root.right = add(root.right, num);
//        }
//        return root;
//    }
}
